/*
 * com.future CO.,ltd.
 */
package com.future.interview;

/**
 * Description: 面试题 08.14. 布尔运算（大厂刷题班10）
 * 给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。
 * 实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/boolean-evaluation-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/4/3:11:15
 */
public class Solution_0814_countEval {

    public static void main(String[] args) {
        /**
         * 1^(0|(0|1))
         * 1^((0|0)|1)
         */
        String s = "1^0|0|1";
        int result = 0;

        s = "0&0&0&1^1|0";
        result = 1;
        System.out.println(countEval(s, result));
        System.out.println(countEval_dp(s, result));
    }

    /**
     * dp版本
     * @param s
     * @param result
     * @return
     */
    public static int countEval_dp(String s, int result) {
        if (s == null || s.equals("")) {
            return 0;
        }
        char[] exp = s.toCharArray();
        int N = exp.length;
        Info[][] dp = new Info[N][N];
        Info allInfo = func_dp(exp, 0, exp.length - 1, dp);
        return result == 1 ? allInfo.trueNum : allInfo.falseNum;
    }

    /**
     * 思路：每一种运算符都可能是作为最后的运算
     * eg:
     * express="1^0|0|1"
     * ---》1    ^   0   |   0   |   1
     * ---》0    1   2   3   4   5   6
     * 位置1的字符作为最后的运算时，等价于1^(0|0|1)
     * 位置3的字符作为最后的运算时，等价于(1^0)|(0|1)
     * 位置5的字符作为最后的运算时，等价于(1^0|0)|1
     * 假设位置i=3的‘|’运算符，即(1^0)|(0|1)
     * 只需要计算i=3的左边，运算结果为1的方法数，lTure，
     * 需要计算i=3的左边，运算结果为0的方法数，lFalse
     * 需要计算i=3的右边，运算结果为1的方法数，rTrue
     * 需要计算i=3的右边，运算结果为0的方法数,rFalse
     * 那么i=i作为最后的运算时，结果为true(即1)=lTure*rTrue+lTrue*rFalse+lFalse*rTrue
     * .....
     * <p>
     * <p>
     * 限制:
     * L...R上，一定有奇数个字符
     * L位置的字符和R位置的字符，非0即1，不能是逻辑符号！
     * 返回str[L...R]这一段，为true的方法数，和false的方法数
     *
     * @param str
     * @param L   必须是数
     * @param R   必须是数
     * @param dp
     * @return L...R上，结果为1的方法数，结果为0的方法数
     */
    public static Info func_dp(char[] str, int L, int R, Info[][] dp) {
        if (dp[L][R] != null) {
            return dp[L][R];
        }
        int t = 0;
        int f = 0;
        if (L == R) {
            t = str[L] == '1' ? 1 : 0;
            f = str[L] == '0' ? 1 : 0;
        } else { // L..R >=3
            // 每一个种逻辑符号，split枚举的东西
            // 都去试试最后结合
            for (int split = L + 1; split < R; split += 2) {
                // 计算L..split-1，结果为1的方法数，结果为0的方法数
                Info leftInfo = func_dp(str, L, split - 1, dp);
                // 计算split+1..R，结果为1的方法数，结果为0的方法数
                Info rightInfo = func_dp(str, split + 1, R, dp);
                int a = leftInfo.trueNum;
                int b = leftInfo.falseNum;
                int c = rightInfo.trueNum;
                int d = rightInfo.falseNum;
                switch (str[split]) {
                    case '&': // 都真为真
                        t += a * c;
                        f += b * c + b * d + a * d;
                        break;
                    case '|': // 一真必真
                        t += a * c + a * d + b * c;
                        f += b * d;
                        break;
                    case '^': // 不同为真
                        t += a * d + b * c;
                        f += a * c + b * d;
                        break;
                }
            }

        }
        dp[L][R] = new Info(t, f);
        return dp[L][R];
    }

    public static int countEval(String s, int result) {
        if (s == null || s.length() % 2 == 0) {
            return 0;
        }
        Info allInfo = process(s, 0, s.length() - 1);
        return result == 1 ? allInfo.trueNum : allInfo.falseNum;
    }


    /**
     * 暴力超时
     * 限制:
     * L...R上，一定有奇数个字符
     * L位置的字符和R位置的字符，非0即1，不能是逻辑符号！
     * 返回str[L...R]这一段，为true的方法数，和false的方法数
     */
    private static Info process(String s, int L, int R) {
        int trueNum = 0;
        int falseNum = 0;
        if (L == R) {
            trueNum = s.charAt(L) == '1' ? 1 : 0;
            falseNum = s.charAt(L) == '0' ? 1 : 0;
        } else {
            /**
             * [L..L] [运算符] [L+2,R]
             * [L..L+2] [运算符] [L+4,R]
             * .....
             * 以[运算符]为最后合并的，收集所有结果为1和0的个数
             *
             * 注意：i位置为运算符位置，因为隔一个位置就是一个运算符（+2）
             */
            for (int i = L + 1; i < R; i += 2) {
                Info lInfo = process(s, L, i - 1);
                Info rInfo = process(s, i + 1, R);
                int lT = lInfo.trueNum;
                int lF = lInfo.falseNum;
                int rT = rInfo.trueNum;
                int rF = rInfo.falseNum;
                switch (s.charAt(i)) {
                    case '&':
                        trueNum += lT * rT;
                        falseNum += lT * rF + lF * rT + lF * rF;
                        break;
                    case '|':
                        trueNum += lT * rF + lT * rT + lF * rT;
                        falseNum += lF * rF;
                        break;
                    case '^':
                        trueNum += lT * rF + lF * rT;
                        falseNum += lT * rT + lF * rF;
                        break;
                }
            }
        }
        return new Info(trueNum, falseNum);
    }

    private static class Info {

        public int trueNum;

        public int falseNum;

        public Info(int trueNum, int falseNum) {
            this.trueNum = trueNum;
            this.falseNum = falseNum;
        }

    }
}
